#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。
示例 1：

输入：nums = [10,5,2,6], k = 100
输出：8
解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2],、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。
示例 2：

输入：nums = [1,2,3], k = 0
输出：0

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subarray-product-less-than-k
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 *
 * */

//妈的超时
static int numSubarrayProductLessThanK1(vector<int> &nums, int k) {

    if (k <= 1)return 0;
    //sort(nums.begin(),nums.end(),greater<int>());

    int count_num = 0;
    for (int i = 0; i < nums.size(); ++i) {

        int temp_sum = 1;//临时和

        for (int j = i; j < nums.size(); ++j) {
            if (nums[j] >= k)
                break;
            temp_sum = temp_sum * nums[j];
            if (temp_sum < k)
                ++count_num;
            else
                break;
        }


    }


    return count_num;
}


static int numSubarrayProductLessThanK(vector<int> &nums, int k) {
    if (nums.size() == 0 || k == 0) return 0;

    int count_num = 0;//结果集

    //[10,5,2,6] 双指针 开始都指向头部
    int low = 0, high = 0;

    //其中算长度就行（当尾指针+的时候）例如
    // 第一次 为high-low+1=1(low=0 high=0) 类似统计了  10
    // 第2次 为high-low+1=2 (low=0 high=1) 类似统计了  10-5  5
    // 第3次 为high-low+1=2 (low=1 high=2) 类似统计了  5-2   2
    // 第3次 为high-low+1=2 (low=1 high=3) 类似统计了  5-2-6  6  2-6
    //[10]、[5]、[2],、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。

    //如果low>high 需要重新赋值sum

    int sum = nums[0];
    while (high < nums.size() && low < nums.size()) {
        if (sum < k) {
            int len = high - low + 1;
            count_num = count_num + len;

            high++;//尾指针+

            //如果high 越界
            if (high >= nums.size())
                return count_num;

            //否则sum增加
            sum = sum * nums[high];

        } else {
            sum = sum / nums[low];//如果low 没有超过high 则 sum/low的数值 因为low准备往后加了
            low++;

            //如果加完后 小于等于high 且还没超过数组
            if (low >= high && low < nums.size()) {
                high = low;
                sum = nums[low];
            }


        }


    }

    return count_num;
}